The present invention relates to a route selection method for telecommunications networks and, more particularly, to an adaptive routing control method which permits optimum routing according to the network status (trunk usage, offered traffic volume, or congestion conditions).
In telecommunications networks with a plurality of switching nodes routes for interconnecting them usually include a first route which achieves the most economical call connection between each originating-terminating node pair. When the first route is not busy, the first route is used to interconnect the originating and terminating nodes, whereas when the first route is busy, alternates routes can be established via one or more other switching nodes. With such a conventional route selection algorithm, however, switching nodes through which alternate routes can be established are limited and the order of their selection also is fixed because of technical restrictions inherent to the call-connection control system employed.
With the recent introduction of switching nodes of a stored program control system and a common channel signaling inter-office system for an inter-office signal transfer, it has become possible to utilize, in place of the above-mentioned route selection algorithm, a dynamic routing method which affords flexible routing based on the distribution of idle trunks in the network.
The dynamic routing method may be classified into time-dependent routing and state-dependent routing (see B. R. Hurley, et al., "A Survey of Dynamic Routing Methods for Circuit Switched Traffic," IEEE COMMUNICATIONS MAGAZINE, Vol. 25, No. 9, pp. 13-21, September 1987, for example).
The time-dependent routing is a method in which a suitable routing pattern is preset for each predetermined time slot, i.e. a method in which a set of alternate routes and the order of their selection are preset for each first route and a call originating in a switching node is connected to the intended destination node, following the routing pattern preset for the time slot concerned. A typical example of the time-dependent routing is a DNHR (Dynamic Nonhierarchical Routing) system proposed by AT & T, Inc. of the United States (see G. R. Ash, et al., "Design and Optimization of Networks with Dynamic Routing," BSTJ, Vol. 60, pp. 1787-1820, October 1981, for instance).
The state-dependent routing is a method which performs a call connection while updating the routing pattern in real time in accordance with the network status such as trunk usage in the network. This method is implemented by centralized or distributed control.
In the state-dependent routing method by centralized control a network control center collects data about the trunk usage throughout the network, calculates a routing pattern between each originating-terminating node pair, and indicates the routing pattern to each switching node in real time. An example of this state-dependent routing method by centralized control is a TSMR system proposed by AT & T, Inc. of the United States and a DCR system by Northern Telecom of Canada (see the afore-mentioned literature by B. R. Hurley, et al., for instance).
In the state-dependent routing method by distributed control each switching node independently detects the network status and autonomously searches for an alternate route based on the network status information, thereby setting an appropriate routing pattern between an origin-destination node pair. Examples of this method are those proposed by British Telecommunications of Great Britain and Centre National D'etudes des Telecommunications of France (commonly known as "CENT"). Both methods are common in basic principle, and the method by British Telecommunications is called a DAR system (see B. R. Stacey, et al., "Dynamic Alternative Routing in the British Telecom Trunk Network," International Switching Symposium, ISS-87, B12.4.1-B.12.4.5, 1987, or Hennion B., "Feedback Methods for Calls Allocation on the Crossed Traffic Routing," International Teletraffic Congress, ITC-9, pp. HEENNION-1 to HENNION-3, 1979, for example).
Some proposals have been made so far for the dynamic routing as mentioned above but they have the following problems yet to be solved for practical use.
(i) The time-dependent routing of the aforementioned DNHR system, for instance, would work well in a country like the United States where a plurality of standard times are used, the traffic busy hour differs sharply with regions, an appropriate routing pattern for each time slot can be forecast, and updating of the routing pattern can be scheduled. Where the traffic busy hour is common almost all over the country as in Japan, however, the time-dependent routing, if used singly, would not be so effective. In a country like Japan it is of prime importance to efficiently handle offered traffic, quickly responding to an excess or shortage of the trunk-number of transit links which is caused by restrictions on the management of trunk resources such as the trunk assignment interval, the trunk modularity, etc. or unpredictable traffic variations, and the state-dependent routing is more effective rather than the time-dependent routing.
(ii) In general, the state-dependent routing by centralized control permits efficient routing, because a routing pattern can be indicated based on the optimization of the entire network through observation of its status, for example, the trunk usage in the network. However, in the case where the observation cycle is long or an information transfer delay occurs, that is, where a time lag is great between the observation and the execution of a call connection by a routing pattern based on the observation, the state of the network varies during this time resulting in an increase in the probability of effecting erroneous control. This will not produce the intended effect and will lower the call-connection quality.
To avoid such a problem and hence achieve the intended effect, it is necessary to reduce the network status observation cycle and the switching node control cycle. The aforementioned TSMR or DCR system, for example, premises that both cycles are within 10 seconds. In a large-scale telecommunications network in which the number of switching nodes to be controlled is several hundreds and the number of links to be measured is as large as tens of thousands, however, such a high-speed observation and control are difficult. In other words, the amount of data to be processed by the network control center, the amount of data to be transferred between the switching nodes and the network control center, and measurements in the switching nodes and the amount of data to be transmitted and received among them are enormous and the facilities therefor are also vast, resulting in an uneconomical system. In addition, a failure in the control center of such a large-scale network will throw the network into disorder.
(iii) With the a aforementioned DAR system and the self-routing system in the state-dependent routing by distributed control, no network control center is employed and each switching node checks the status of alternate routes by a signal handled in its call-connection procedure and autonomously changes an alternate route accordingly, thereby implementing a preferably routing pattern throughout the telecommunications network. Consequently, the problem mentioned above in (ii) can be avoided. In a large-scale telecommunications network, however, the number of alternate routes for each origin-destination node pair becomes appreciable, incurring various disadvantages. For instance, in a telecommunications network which forms a mesh by 100 switching nodes the number of alternate routes via two transit links between each origin-destination node pair alone is as large as 98.
In such an instance, (a) alternate routes are rechecked through a search by trial and error prior to a call-connection procedure, and consequently, when the number of available alternate routes is unnecessarily large, the search is repeated inevitably many times until a routing pattern updated according to temporary traffic variations is restored to its initial state. Similarly, when a traffic pattern throughout the network changes or transmission equipment breaks down, the search is repeated many times until each switching node shifts to a new favorable routing pattern. This will deteriorate the call-connection quality and increase the amount of data to be processed by each switching node. (b) An increase in the amount of data managed by each switching node calls for an increase in the number of tables for processing data and the number of counters for counting the number of calls. That is to say, the amount of data which is managed for each origin-destination node pair or each first route increases, and consequently, alternate route tables are required and the state of alternate routing must be monitored from the viewpoint of network management. This necessitates a number of counters for counting the number and the traffic volume of alternate calls and the transit-call-completion probability in each alternate route. Moreover, (c) an increase in the number of counters used will cause an increase in the computer running time to be processed for measurement by the counters.